package com.cat.dynamicPlanning;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/strange-printer/
 * @create 2025/9/8 09:28
 * @since JDK17
 */

public class Solution93 {
    public int strangePrinter(String str) {
        char[] s = str.toCharArray();
        int n = s.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n - 1; i++) {
            dp[i][i] = 1;
            dp[i][i + 1] = s[i] == s[i + 1] ? 1 : 2;
        }
        dp[n - 1][n - 1] = 1;
        for (int l = n - 3; l >= 0; l--) {
            for (int r = l + 2; r < n; r++) {
                if (s[l] == s[r]) {
                    dp[l][r] = dp[l + 1][r];
                } else {
                    dp[l][r] = Integer.MAX_VALUE;
                    for (int k = l; k < r; k++) {
                        dp[l][r] = Math.min(dp[l][r], dp[l][k] + dp[k + 1][r]);
                    }
                }
            }
        }
        return dp[0][n - 1];
    }
}
